package com.c2b.algorithm.newcoder.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * <a href="https://www.nowcoder.com/practice/0bf071c135e64ee2a027783b80bf781d?tpId=295&tqId=1512964&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">二叉树的中序遍历</a>
 * <p>给定一个二叉树的根节点root，返回它的中序遍历结果。</p>
 * <p>
 * 数据范围：树上节点数满足0≤n≤1000，树上每个节点的值满足−1000≤val≤1000<br>
 * 进阶：空间复杂度O(n)，时间复杂度O(n)
 * </p>
 *
 * @author c2b
 * @since 2023/3/13 15:22
 */
public class BM0024InorderTraversal_M {

    public int[] inorderTraversal(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        // 辅助栈
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> resList = new ArrayList<>();
        // 将当前节点及其所有左右左子节点入栈
        while (!stack.empty() || root != null) {
            // 把当前节点的所有左子节点依次压入栈
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            resList.add(root.val);
            // 进入右节点
            root = root.right;
        }
        int[] resArray = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            resArray[i] = resList.get(i);
        }
        return resArray;
    }

    public int[] inorderTraversal2(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        List<Integer> resList = new ArrayList<>();
        recursion(resList, root);
        int[] resArray = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            resArray[i] = resList.get(i);
        }
        return resArray;
    }

    private void recursion(List<Integer> resList, TreeNode root) {
        // 左
        if (root.left != null) {
            recursion(resList, root.left);
        }
        // 根
        resList.add(root.val);
        // 右
        if (root.right != null) {
            recursion(resList, root.right);
        }
    }

    public static void main(String[] args) {
        //TreeNode treeNode = new TreeNode(4);
        //treeNode.left = new TreeNode(5);
        //treeNode.right = new TreeNode(3);
        //treeNode.left.left = new TreeNode(6);
        //treeNode.right.left = new TreeNode(1);
        //treeNode.right.right = new TreeNode(0);
        //treeNode.right.left.right = new TreeNode(9);
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        BM0024InorderTraversal_M bm0024InorderTraversal_m = new BM0024InorderTraversal_M();
        for (int i : bm0024InorderTraversal_m.inorderTraversal2(treeNode)) {
            System.out.println(i);
        }
    }
}
